package dataStructures.list;

/**
 * A generic singlely linked node, that contains only a pointer to the data
 * and the next node. Contains a static sentinel node that contains null and
 * points to itself.
 * 
 * Fully Tested: Yes
 * Fully Documented: Yes
 * Created: 2011
 * Last Modified: Nov 9, 2011
 * 
 * @author Shimu Wu
 */
public class SinglelyLinkedNode<T> {

    /** The sentinel node, containing the value null and a pointer to
     itself */
    public final static SinglelyLinkedNode sentinel
            = new SinglelyLinkedNode(null);
    static {
        sentinel.next = sentinel;
    }
    
    /** The data being stored by this node */
    protected T data;

    /** The next node */
    protected SinglelyLinkedNode<T> next;

    /**
     * Instantiates a SinglelyLinkedNode with the given data. The next
     * node is set to null.
     * 
     * @param data the data to be stored in the new node 
     */
    protected SinglelyLinkedNode(T data) {
        this(data, null);
    }

    /**
     * Instantiates a SinglelyLinkedNode with the given data. The next
     * node is set to null.
     * 
     * @param data the data to be stored in the new node
     * @param next the next SinglelyLinkedNode
     */
    protected SinglelyLinkedNode(T data, SinglelyLinkedNode<T> next) {
        this.data = data;
        this.next = next;
    }

    /**
     * Returns the next SinglelyLinkedNode, and set this node's next pointer
     * to null
     * @return the next node
     */
    public SinglelyLinkedNode<T> popNext(){
        SinglelyLinkedNode<T> returnNode = this.next;
        this.next = null;
        return returnNode;
    }

    /**
     * Assuming this SinglelyLinkedNode is the start of a linked list,
     * cuts the list at the given index and returns the SinglelyLinkedNode
     * that starts the cut off list.
     * @param index the index to cut off the linked list
     * @return a SinglelyLinkedNode that points to the start node of the
     * cut off list
     */
    public SinglelyLinkedNode<T> cut(int index) {
        int i = 1;
        SinglelyLinkedNode<T> current = this;
        while ((i < index) && (current != null)) {
            current = current.next;
            i++;
        }
        if (current == null) {
            return null;
        } else {
            SinglelyLinkedNode<T> newListStart = current.next;
            current.next = null;
            return newListStart;
        }
    }

    /*
    public SinglelyLinkedNode<T> cutInHalf() {
        
        SinglelyLinkedNode<T> slow, fast;
        slow = this;
        fast = this.next;
        while ((slow != null) && (fast != null)){
            slow = slow.next;
            fast = fast.next.next;
        }
    }
     * 
     */
}
